1. Field of the Invention
This invention relates to computer systems and, more specifically, to shared memory architectures.
2. Background Information
A computer system typically comprises one or more processors linked to a main memory by a bus or other interconnect. In most computer systems, main memory organizes the instructions and data being stored into units typically referred to as “blocks”, each of which is separately addressable and may be of a fixed size. Instructions and data are typically moved about the computer system in terms of one or more blocks.
Ordinarily, a processor will retrieve data, e.g., one or more blocks, from main memory, perform some operation on it, and eventually return the results back to main memory. Retrieving data from main memory and providing it to a processor can take significant time especially in terms of the high operating speeds of processors. To reduce such latencies as well as to reduce the number of times a processor must access main memory, modern processors and/or processor chipsets include one or more cache memories or caches. A cache is a small, fast memory module that is placed in close proximity to the processor. Many caches are static random access memories (SRAMs), which are faster, but more expensive, than dynamic random access memories (DRAMs), which are often used for main memory. The cache is used to store information, e.g., data or instructions, which the processor is currently using or is likely to use in the near future. There are two basic types of caches: “write-through” caches and “write-back” caches.
With a write-through cache, whenever a processor modifies or updates a piece of data in the processor's cache, main memory's copy of that data is automatically updated. This is accomplished by having the processor write the data back to memory whenever the data is modified or updated. A write-back cache, in contrast, does not automatically send modified or updated data to main memory. Instead, the updated data remains in the cache until some more convenient time, e.g., when the processor is idle, at which point the modified data is written back to memory. The utilization of write-back caches typically improves system performance. In some systems, a write-back or victim buffer is provided in addition to the cache. “Victim data” refers to modified data that is being removed from the processor's cache in order to make room for new data received at the processor. Typically, the data selected for removal from the cache is data the processor is no longer using. The victim buffer stores this modified data which is waiting to be written back to main memory.
Symmetrical Multiprocessor (SMP) Systems
Multiprocessor computing systems, such as symmetrical multiprocessor (SMP) systems, provide a computer environment in which software applications may run on a plurality of processors using a single address space or shared memory abstraction. In a shared memory system, each processor can access any data item without a programmer having to worry about where the data is or how to obtain its value. This frees the programmer to focus on program development rather than on managing partitioned data sets and communicating values.
Cache Coherency
Because more than one processor of the SMP system may request a copy of the same memory block from main memory, cache coherency protocols have been developed to ensure that no processor relies on a memory block that has become stale, typically due to a modification or update performed to the block by some other processor. Many cache coherency protocols associate a state with each cache line. A given memory block, for example, may be in a shared state in which copies of the block may be present in the caches associated with multiple processors. When a memory block is in the shared state, a processor may read from, but not write to, the respective block. To support write operations, a memory block may be in an exclusive state. In this case, the block is owned by a single processor which may write to the cache line. When the processor updates or modifies the block, its copy becomes the most up-to-date version, while corresponding copies of the block at main memory and/or other processor caches become stale.
When a processor wishes to obtain exclusive ownership over a memory block that is currently in the shared state (i.e., copies of the block are present in the caches of other processors) invalidate requests are typically issued to those other processors. When an invalidate request is received by a given processor, its cache is searched for the specified memory block. If the block is found, it is transitioned to an invalid state. Many caches assign or associate a valid bit with each memory block or cache line stored in the cache. If the bit is asserted, then the cache line is considered to be valid and may be accessed and utilized by the processor. When a memory block is initially received from main memory, the valid bit is asserted and the memory block is stored in the cache. When an invalidate request is received, the valid bit of the respective cache line is de-asserted, thereby indicating that the cache line is no longer valid.
There are two classes of cache coherency protocols: snooping and directory based. With snooping, the caches monitor or snoop all transactions traversing the shared memory bus, looking for transactions that reference a memory block stored at the cache. If such a transaction is detected, the cache updates the status information for its copy of the memory block based on the snoop transaction. In this way, every cache that has a copy of a given memory block also has a copy of the status information of that block. With a directory based protocol, the state of each block is kept in a single, centralized location in the system, called a directory. Status information is not maintained in the individual caches.
FIG. 1 is a highly schematic illustration of a prior art directory 100. Directory 100 has a plurality of entries 102a–d each of which corresponds to a respective memory block. The directory 100 is organized, moreover, such that each entry 102a–d has a plurality of fields or cells for storing state and/or status information for the respective block. In particular, the directory 100 has an address column 103 that stores the address of the memory block, an owner column 104 that stores the identity of the entity, e.g., a processor or main memory itself, that is considered to be the owner of the memory block, and a sharer column 106 that stores the identity of those processors or other system entities that have a shared copy of the block.
The sharer column 106 may have a plurality of sub-columns 106a–c, each of which may contain the identity of a processor or a collection of processors that may have a shared copy of the respective memory block. If a request for shared access to a memory block is received from a first processor, P1, main memory examines the directory entry, e.g., entry 102c, for the block to determine its owner. As memory is itself the owner of the block, memory sends its copy of the block to P1 and enters P 1's identifier (ID) into one of the sharer fields, e.g. field 106b, of the respective directory entry, e.g., entry 102c, thereby noting that P1 has a shared copy of the block. Since P1 only requested shared access to the memory block, the contents of the entry's owner field 104 are not modified.
If P1 issues a request for exclusive or write access to some other memory block, e.g., the block corresponding to entry 102d, main memory again examines the contents of entry 102d. Suppose that, at the time the request is received, the owner field reflected that memory was the owner of the memory block as shown in parentheses. In this case, memory sends the block to P1, and replaces the contents of the owner field 104 with P1's ID to reflect that P1, rather than memory, is now the owner of the memory block. P1 may then modify or update the memory block. If a request from a second processor, e.g., processor P2, is subsequently received for a shared copy of this memory block, main memory examines entry 102d of the directory 100 and determines that P1 is the owner of the memory block. Because its copy of the block, i.e., the copy stored at main memory, may be stale, memory does not forward its copy to P2. Instead, memory may be configured to forward the request to P1 and add P2's ID to one of the sharer fields, e.g., field 106a. In response to the forwarded request, P1 may then supply P2 with a copy of the modified memory block from P1's cache. Alternatively, main memory may be configured to force P1 to relinquish ownership of the memory block and return the modified version to memory so that memory can send a copy of the up-to-date version to P2.
In addition, many computer systems are designed to notify the directory when a “clean” memory block is being victimized from a cache to make room for a new block. A clean memory block is an unmodified block to which the processor had read, i.e., shared, access. Specifically, a processor may issue a Victim_Clean message to the directory notifying it that the processor is victimizing its clean copy of a block. Because the block is in the clean state, the processor does not have to return a copy of the clean block to the directory. Upon receipt of the Victim_Clean message, the directory updates its lists of sharers of the block by deleting the processor as one of the block's sharers. The directory is thus kept up-to-date as to which processors still have shared copies of the block. If an entity subsequently requests exclusive or write access to the block, invalidate messages are only sent from the directory to those entities still listed as having a shared copy of the block. Invalidate messages are not to those processors that issued Victim_Clean messages for the block as these processors have been removed from the directory's list of sharers.
In a computer system that relies on Victim_Clean messages to remove a processor from a list of sharers, the amount of directory state that is provided must scale with the size of the system so that each potential sharer can be exactly identified in the directory. This is not typically done in large computer systems as the amount of directory storage required to list all possible sharers is overly burdensome. In large computer systems, the identity of shares is often abbreviated in the directory using a coarse vector, each bit of which corresponds to a group (as opposed to one) processor. A Victim_Clean message that sees a coarse vector in the sharer list is unable to update directory state, due to the fact that another processor assigned to the same bit targeted by the Victim_Clean message may also have a cached copy of the block. Clearing the bit could erroneously indicate that no processors represented by that bit have a shared copy when in fact one or more of the processors may have a shared copy. Thus, Victim_Clean messages cannot be used to keep a sharer list up-to-date in such directories.
Other computer systems have been designed such that processors do not issue Victim_Clean messages. That is, if a processor victimizes a clean block from its cache, the processor does not issue a Victim_Clean message to the directory. For example, some directories use a coarse vector to track those entities having a shared or read access copy of a memory block, rather than specifically identifying each such processor. Each bit of a coarse vector tracks a group of processors any one or more of which may have a shared copy of the respective block. Victim_Clean messages cannot be used in this case as the directory does not know whether the source of the Victim_Clean was the only processor of the group have a copy of the block. Although this approach reduces communication overhead, thereby improving bandwidth, it results in the state of the directory becoming stale. That is, in the absence of a Victim_Clean message and a method to correlate the Victim_Clean to a value in the sharer column, as necessary, the directory may continue to indicate that a processor has a shared copy of a block when, in fact, the processor has victimized the block from its cache. This can lead to confusion or ambiguity when an invalidate is sent to the processor at the same time that the processor is issuing another request for the same block. More specifically, to obtain another copy of the block that is previously victimized, the processor issues a Read request. If, however, some other entity requests exclusive access to the block, the directory will issue an invalidate to the processor as the directory continues to reflect that the first processor has a shared copy of the block in its cache. When the invalidate is received at the processor, it cannot tell whether the invalidate applies to the version of the block that the processor victimized or to the new version that the processor has requested.
To eliminate the confusion, these systems utilized markers and required that the communication channels between the processors and main memory be ordered. When the directory is accessed in response to some request by entity, e.g., for read or write access to a block, the directory issues a marker message to the entity thereby notifying it that the directory has been accessed. The directory may thereafter issue other messages depending on the state of the directory, such a Fill message, invalidates, etc. If a processor, that is requesting another copy of a block that it victimized from its cache, receives an invalidate before the marker message, the processor “knows” that the invalidate applies to the earlier version of the block that was previously stored in its cache. If the marker message is received before an invalidate, then the processor “knows” that the invalidate applies to the current version of the block that the processor is requesting. This is so because the marker and invalidate messages are delivered in the same order that is they are sent. Accordingly, the use of marker messages and ordered channels allows the processors to determine to which version of a memory block a received invalidate applies.